// https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/comments/
// Created by ade on 2022/11/10.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Solution {
public:
    vector <vector<int>> kSmallestPairs(vector<int> &nums1, vector<int> &nums2, int k) {
        vector <vector<int>> res = {};
        auto cmp = [&](pair<int,int> &a, pair<int,int> &b) {
            return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
        };
        priority_queue < pair<int,int> , vector < pair<int,int>>, decltype(cmp) > pq(cmp);
        int len1 = nums1.size(), len2 = nums2.size();
        for (int i = 0; i < len1; i++)
            pq.push({i, 0});
        while (res.size() < k && (long)res.size() < (long)len1 * len2) {
            auto top = pq.top();
            pq.pop();
            if (top.second + 1 < len2) {
                pq.push({top.first, top.second + 1});
            }

            res.push_back(vector < int > {nums1[top.first], nums2[top.second]});
        }

        return res;
    }
};

int main() {
    Solution so;
    vector<int> nums1 = {1, 1, 2};
    vector<int> nums2 = {1, 2, 3};
    auto res = so.kSmallestPairs(nums1, nums2, 10);
    for (auto &d:res) {
        cout << d[0] << "-" << d[1] << endl;
    }
    return 0;
}